<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Document</title>
    </head>
    <body>
        <script>
            /*
            从上到下遍历每一个节点，如果第一次遍历到的节点的值处于[p,q]之间，
            那么该值就是最近公共祖先。
            这是因为p，q一定存在于它的左右子树中
            */
            var lowestCommonAncestor = function (root, p, q) {
                if (!root) return null
                /* 因为你不知道p，q哪个大呀 */
                if (root.val >= p.val && root.val <= q.val) {
                    return root
                }
                if (root.val <= p.val && root.val >= q.val) {
                    return root
                }
                if (root.val > p.val && root.val > q.val) {
                    // 向左子树查询
                    return lowestCommonAncestor(root.left, p, q)
                }
                if (root.val < q.val && root.val < p.val) {
                    return lowestCommonAncestor(root.right, p, q)
                }
            }
        </script>
    </body>
</html>
